/*
============================================================================
Name        : dd_avl.c
Author      : Jian (raphyer@hotmail.com)
Version     :
Copyright   : GPL
Description : dd_avl.c - source file
============================================================================
*/

/* INCLUDE FILES */
#include "dd_avl.h"


/* MACROS */
#define __update_height(n)  if((n)) (n)->height = 1 + DD_MAX(_node_height((n)->left_child), _node_height((n)->right_child))



static dd_avl_node* _init_node(dd_avl_key* key, dd_avl_value* value)
{
    dd_avl_node* node = (dd_avl_node*)DD_MALLOC(sizeof(dd_avl_node)) ;
    node->key         = key ;
    node->value       = value ;
    node->left_child  = DD_NULL ;
    node->right_child = DD_NULL ;
    node->height      = 1 ;
    return node ;
}

static void _deinit_node(dd_avl_node* node)
{
    if (node) {
        _deinit_node(node->left_child) ;
        _deinit_node(node->right_child) ;
        __do_destroy(node) ;
    }
}

static void _deinit_empty_node(dd_avl_node* node)
{
    if (node) {
        __do_destroy(node) ;
    }
}

static __dd_inline__ _is_leaf(const dd_avl_node* node)
{
    return !node->left_child && !node->right_child ;
}


static __dd_inline__ DD_INT _node_height(const dd_avl_node* node)
{
    /* It is too slow 
    if (node) {
        DD_INT left_height  = 0 ;
        DD_INT right_height = 0 ;
        
        if (node->left_child)
            left_height = _node_height(node->left_child);
        
        if (node->right_child)
        right_height = _node_height(node->right_child) ; 
        return 1 + DD_MAX(left_height, right_height) ;
    }
    */ 

    return node ? node->height : 0 ;
}


static __dd_inline__ DD_INT _abs(DD_INT num)
{
    return (num < 0) ? (-num) : num ;
}


/* Lost balance with inserting new_node to node->left_child->left_child should do a single left rotation */
static void _signal_left(dd_avl_node* node)
{
    dd_avl_node* tmp_node   = node->left_child ;
    dd_avl_key* tmp_key     = DD_NULL ;
    dd_avl_value* tmp_value = DD_NULL ;

    node->left_child        = tmp_node->left_child ;
    tmp_node->left_child    = tmp_node->right_child ;
    tmp_node->right_child   = node->right_child ;
    node->right_child       = tmp_node ;
    
    tmp_key                 = tmp_node->key ;
    tmp_value               = tmp_node->value ;
    tmp_node->key           = node->key ;
    tmp_node->value         = node->value ;
    node->key               = tmp_key ;
    node->value             = tmp_value ;
    
    __update_height(tmp_node) ;
    __update_height(node) ;
}

/* Lost balance with inserting new_node to node->right_child->right_child should do a single right rotation */
static void _signal_right(dd_avl_node* node)
{
    dd_avl_node* tmp_node   = node->right_child ;
    dd_avl_key* tmp_key     = DD_NULL ;
    dd_avl_value* tmp_value = DD_NULL ;

    node->right_child       = tmp_node->right_child ;
    tmp_node->right_child   = tmp_node->left_child ;
    tmp_node->left_child    = node->left_child ;
    node->left_child        = tmp_node ;

    tmp_key                 = tmp_node->key ;
    tmp_value               = tmp_node->value ;
    tmp_node->key           = node->key ;
    tmp_node->value         = node->value ;
    node->key               = tmp_key ;
    node->value             = tmp_value ;

    __update_height(tmp_node) ;
    __update_height(node) ;
}

/* Lost balance with inserting new_node to node->left_child->right_child should do a double rotation */
static void _double_left_right(dd_avl_node* node)
{
    _signal_right(node->left_child) ;
    _signal_left(node) ;
}


/* Lost balance with inserting new_node to node->right_child->left_child should do a double rotation */
static void _double_right_left(dd_avl_node* node)
{
    _signal_left(node->right_child) ;
    _signal_right(node) ;
}


static void _insert(dd_avl_tree* avl, dd_avl_node* node, dd_avl_key* key, dd_avl_value* value)
{
    int cmp = 0 ;

    __DD_ASSERT_DEFENSE(avl && node && key, return) ;

    if (node->key == DD_NULL) {
        __DD_ASSERT(node == avl->root) ;
        node->key    = key ;
        node->value  = value ;
        __update_height(node) ;
        return ;
    }

    cmp = avl->key_compare(key, node->key) ;

    if (cmp < 0) {
        
        if (node->left_child) {

            _insert(avl, node->left_child, key, value) ;
            
            /* Check if lost balance */
            if (_node_height(node->left_child) - _node_height(node->right_child) > 1) {
                if (avl->key_compare(key, node->left_child->key) < 0)
                    _signal_left(node) ;
                else 
                    _double_left_right(node) ;
            }
        }
        else 
            node->left_child = _init_node(key, value) ;

        __update_height(node) ;

        return ;
    }

    if (cmp > 0) {
        
        if (node->right_child) {

            _insert(avl, node->right_child, key, value) ;
            
            /* Check if lost balance */
            if (_node_height(node->right_child) - _node_height(node->left_child) > 1) {
                if (avl->key_compare(key, node->right_child->key) < 0)
                    _double_right_left(node) ;
                else 
                    _signal_right(node) ;
            }
        }
        else
            node->right_child = _init_node(key, value) ;

        __update_height(node) ;

        return ;
    }

    /* cmp = 0 */
    avl->key_conflict(node->key, node->value, key, value) ;
}


dd_avl_tree* dd_avl_create(
    DD_INT (*key_compare)(const dd_avl_key*, const dd_avl_key*), 
    void (*key_conflict)(dd_avl_key* , dd_avl_value*, dd_avl_key*, dd_avl_value*) 
) 
{
    dd_avl_tree* avl = (dd_avl_tree*)DD_MALLOC(sizeof(dd_avl_tree)) ;
    DD_MEMSET(avl, 0, sizeof(dd_avl_tree)) ;
    
    avl->root           = _init_node(DD_NULL, DD_NULL) ;
    avl->key_compare	= key_compare ;
    avl->key_conflict	= key_conflict ;
    
    return avl ;
}

void dd_avl_destroy(dd_avl_tree* avl) 
{
    __DD_ASSERT_DEFENSE(avl, return) ;

    _deinit_node(avl->root) ;
    __do_destroy(avl) ;
}


dd_avl_value* dd_avl_find(const dd_avl_tree* avl, dd_avl_key* key)
{
    dd_avl_node* tmp_node = avl->root ;

    __DD_ASSERT_DEFENSE(avl && avl->root && key, return DD_NULL) ;

    Avl_Find:
    if (tmp_node) {
        
        int cmp = avl->key_compare(tmp_node->key, key) ;

        if (cmp < 0) {
            tmp_node = tmp_node->right_child ;
            goto Avl_Find ;
        }

        if (cmp > 0) {
            tmp_node = tmp_node->left_child ;
            goto Avl_Find ;
        }
    
        return tmp_node->value ;        
    }

    return DD_NULL ;
}


void dd_avl_insert(dd_avl_tree* avl, dd_avl_key* key, dd_avl_value* value) 
{
    __DD_ASSERT_DEFENSE(avl && avl->root && key, return) ;

    _insert(avl, avl->root, key, value) ;
}



static void _find_biggest_node(dd_avl_node* node, dd_avl_node* parent, dd_avl_node* remove_node)
{
    if (node->right_child == DD_NULL) {
        
        remove_node->key   = node->key ;
        remove_node->value = node->value ;

        if (parent->left_child == node) 
            parent->left_child = node->left_child ;
        
        if (parent->right_child == node) 
            parent->right_child = node->left_child;
        
        _deinit_empty_node(node) ;
        
        return ;
    }

    _find_biggest_node(node->right_child, node, remove_node) ;
    
    if (_node_height(node->left_child) - _node_height(node->right_child) > 1) {
        if (_node_height(node->left_child->left_child) >= _node_height(node->left_child->right_child))
            _signal_left(node) ;
        else 
            _double_left_right(node) ;
    }

    __update_height(node) ;
}


static void _find_smallest_node(dd_avl_node* node, dd_avl_node* parent, dd_avl_node* remove_node)
{
    if (node->left_child == DD_NULL) {
        remove_node->key   = node->key ;
        remove_node->value = node->value ;

        if (parent->right_child == node)
            parent->right_child = node->right_child ;

        if (parent->left_child == node) 
            parent->left_child = node->right_child ;

        _deinit_empty_node(node) ;
        return ;
    }

    _find_smallest_node(node->left_child, node, remove_node) ;
    
    if (_node_height(node->right_child) - _node_height(node->left_child) > 1) {
        if (_node_height(node->right_child->right_child) >= _node_height(node->right_child->left_child))
            _signal_right(node) ;
        else 
            _double_right_left(node) ;
            
    }

    __update_height(node) ;
}


static void _find_pos_del(dd_avl_tree* avl, dd_avl_node* parent, dd_avl_node* remove_node)
{
    if (remove_node->left_child && remove_node->right_child) {
        
        int height_diff = _node_height(remove_node->left_child) - _node_height(remove_node->right_child) ;

        __DD_ASSERT(_abs(height_diff) <= 1) ;

        if (height_diff == 1)
            _find_biggest_node(remove_node->left_child, remove_node, remove_node) ;
        else 
            _find_smallest_node(remove_node->right_child, remove_node, remove_node) ;

        __update_height(remove_node) ;
    }
    else {
        
        dd_avl_node* child_node = remove_node->left_child ? remove_node->left_child : remove_node->right_child ;
         
        __DD_ASSERT(!child_node || _is_leaf(child_node)) ;
        
        if (parent) {
            if (parent->left_child == remove_node)
                parent->left_child = child_node ;
            else 
                parent->right_child = child_node ;
        }
        else {
            __DD_ASSERT(avl->root == remove_node) ;
            avl->root = child_node ;
        }
        _deinit_empty_node(remove_node) ;
    }
    
    __update_height(parent) ;
}


static dd_avl_value* _remove(dd_avl_tree* avl, dd_avl_node* node, dd_avl_node* parent, dd_avl_key* key)
{
    int cmp           = 0 ;
    dd_avl_value* val = DD_NULL ;
    
    __DD_ASSERT_DEFENSE(avl && node && key, return DD_NULL) ;
    
    cmp = avl->key_compare(key, node->key) ;

    if (cmp == 0) {
        /* Find the delete key */
        val = node->value ;
        _find_pos_del(avl, parent, node) ;
        return val ;
    }

    if (cmp < 0 && node->left_child) {

        val = _remove(avl, node->left_child, node, key) ;
        if (val) {
             /* Check if lost balance: It like to add a child in the Right child */
            if (_node_height(node->right_child) - _node_height(node->left_child) > 1) {
                if (_node_height(node->right_child->right_child) >= _node_height(node->right_child->left_child))
                    _signal_right(node) ;
                else 
                    _double_right_left(node) ;
                    
            }
            __update_height(node) ;
            return val ;
        }
    }
    
    if (cmp > 0 && node->right_child) {
        
        val = _remove(avl, node->right_child, node, key) ;
        
        if (val) {
            /* Check if lost balance: It like to add a child in the Left child */
            if (_node_height(node->left_child) - _node_height(node->right_child) > 1) {
                
                if (_node_height(node->left_child->left_child) >= _node_height(node->left_child->right_child))
                    _signal_left(node) ;
                else 
                    _double_left_right(node) ;
                
            }
            __update_height(node) ;
            return val ;
        }
    }
    
    return DD_NULL ;
}


dd_avl_value* dd_avl_remove(dd_avl_tree* avl, dd_avl_key* key) 
{
    __DD_ASSERT_DEFENSE(avl && avl->root && key, return DD_NULL) ;

    return _remove(avl, avl->root, DD_NULL, key) ;
}


#ifdef __DD_UNITTEST

#include "dd_vector.h"


static DD_INT _test_key_compare(const dd_avl_key* key1, const dd_avl_key* key2) 
{
    if (key1 < key2) return -1 ;
    
    if (key1 > key2) return 1 ;
    
    return 0 ;
}

static void _test_key_conflict(
    dd_avl_key* key_found_conflict, 
    dd_avl_value* value_found_conflict, 
    dd_avl_key* key_handle, 
    dd_avl_value* value_handle
) 
{
    __DD_ASSERT((int)key_found_conflict == (int)value_found_conflict && (int)key_handle == (int)value_handle 
        && (int)key_found_conflict == (int)key_handle) ;
}

static DD_BOOL _ut_check_avl_node(dd_avl_tree* avl, dd_avl_node* node)
{
    if (!node || !(node->key)) return DD_TRUE;

    if (_abs(_node_height(node->left_child) - _node_height(node->right_child)) > 1) 
    {
        DD_LOG("_ut_check_avl_node ERROR 1: check HEIGHT") ;
        return DD_FALSE ;
    }

    if (DD_MAX(_node_height(node->left_child), _node_height(node->right_child)) + 1 != _node_height(node))
    {
        DD_LOG("_ut_check_avl_node ERROR 2: check HEIGHT") ;
        return DD_FALSE ;
    }

    if (node->left_child) {
        if (avl->key_compare(node->left_child->key, node->key) >= 0) {
            DD_LOG("_ut_check_avl_node ERROR : check left_child key") ;
            return DD_FALSE ;
        }
        
        if (!_ut_check_avl_node(avl, node->left_child))
            return DD_FALSE;
    }
    
    if (node->right_child) {

        if (avl->key_compare(node->right_child->key, node->key) <= 0) {
            DD_LOG("_ut_check_avl_node ERROR : check right_child key") ;
            return DD_FALSE ;
        }
        
        if (!_ut_check_avl_node(avl, node->right_child))
            return DD_FALSE;
    }
    
    return DD_TRUE ;
}

static DD_BOOL _ut_check_avl(dd_avl_tree* avl)
{
    // DD_LOG("_ut_check_btree Start to check the node of tree") ;
    
    if (!_ut_check_avl_node(avl, avl->root))
    {
        DD_LOG("_ut_check_avl check tree FAILED") ;
        return DD_FALSE ;
    }

    // DD_LOG("_ut_check_avl check tree SUCCEED") ;

    return DD_TRUE ;
}

static void _ut_print_avl_node(dd_avl_node* node)
{
    if (!node || !node->key) return ; 

    _ut_print_avl_node(node->left_child) ;
    DD_LOG("node key = %d, value = %d", (DD_INT)node->key, (DD_INT)node->value) ;
    _ut_print_avl_node(node->right_child) ;
}


#define __TEST_TIMES            (1000 + 1)
// #define __TEST_RECUR_ERROR


DD_BOOL dd_avl_test() 
{
    dd_avl_tree* test_avl = dd_avl_create(_test_key_compare, _test_key_conflict) ;
    dd_vector* test_vec   = dd_vector_create(__TEST_TIMES) ;
    
    DD_INT i = 0 ;
    
#ifndef __TEST_RECUR_ERROR
    i = 1 ;
    DD_SRAND((DD_UINT)DD_TIME(0)) ;
    for (; i < __TEST_TIMES; i++) {
        void* k = (void*)(DD_RAND());
        // void* k = (void*)i ;
        if (k!= 0 && dd_avl_find(test_avl, k) == DD_NULL) {
            dd_avl_insert(test_avl, k, k) ; 

            if (__TEST_TIMES < 30) {
                DD_LOG("=============== After insert %d ===============", (int)k) ;
                _ut_print_avl_node(test_avl->root) ;
            }

            dd_vector_append(test_vec, k) ;
        }

        if (!_ut_check_avl(test_avl))
            return DD_FALSE ;
    }
    
    if (!_ut_check_avl(test_avl))
           return DD_FALSE ;

    
    i = 1;
    for (; i < dd_vector_count(test_vec); i++)
    {
        if( dd_avl_find(test_avl, dd_vector_get(test_vec, i)) != dd_vector_get(test_vec, i))
        {
            DD_LOG("dd_avl_find find date ERROR") ;
            return DD_FALSE ;
        }
    }

    dd_vector_dump_file(test_vec, "d:\\vec_avl_dump.txt");
   
#else
    
    dd_vector_destroy(test_vec, DD_NULL) ;

    test_vec = dd_vector_read_file("d:\\vec_avl_dump.txt") ;
    
    i = 0 ;

    for (; i < dd_vector_count(test_vec); i++)
    {
        void* k = (void*)dd_vector_get(test_vec, i) ;
        dd_avl_insert(test_avl, k, k) ; 
    }
    
#endif  /* __TEST_RECUR_ERROR */

    i = 1 ;
    for (; i < dd_vector_count(test_vec); i++) {
        
        void* k = (void*)dd_vector_get(test_vec, i) ;

        if (dd_avl_remove(test_avl, k) != k) {
            DD_LOG("dd_avl_remove remove date ERROR %d", (DD_INT)k) ;
            return DD_FALSE ;
        }

        if (__TEST_TIMES < 30) {
            DD_LOG("=============== After remove %d ===============", (int)k) ;
            _ut_print_avl_node(test_avl->root) ;
        }

        if (!_ut_check_avl(test_avl))
            return DD_FALSE ;
    }

    dd_vector_destroy(test_vec, DD_NULL) ;
    dd_avl_destroy(test_avl) ;

    return DD_TRUE ;
}

#endif  /* __DD_UNITTEST */



/* End of File */
